package Leetcode.sliding_window;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @Author: kirito
 * @Date: 2024/3/29 13:42
 * @Description:
 * 几乎唯一子数组的最大和
 * 给你一个整数数组 nums 和两个正整数 m 和 k 。
 *
 * 请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
 *
 * 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
 *
 * 子数组指的是一个数组中一段连续 非空 的元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,6,7,3,1,7], m = 3, k = 4
 * 输出：18
 * 解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。
 * 这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。
 * 示例 2：
 *
 * 输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
 * 输出：23
 * 解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。
 * 这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。
 * 示例 3：
 *
 * 输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
 * 输出：0
 * 解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 104
 * 1 <= m <= k <= nums.length
 * 1 <= nums[i] <= 109
 */

public class maxSum {
    public static void main(String[] args) {
//        List<Integer> list = new ArrayList<Integer>(Arrays.asList(2, 6, 7, 3, 1, 7));
//        int m = 3;
//        int k = 4;
//        list.sort((a, b) -> a - b);
//        System.out.println(list);

    }

    public long maxSum(List<Integer> nums, int m, int k) {
        // 将List转换为int数组，方便使用索引访问
        int[] a = nums.stream().mapToInt(i -> i).toArray();
        long ans = 0, sum = 0; // `ans`用来存储最终结果，`sum`用来存储当前子数组的和
        Map<Integer, Integer> cnt = new HashMap<>(); // `cnt`用来统计当前窗口中每个元素的数量

        // 首先统计k-1个数的和以及每个元素出现的次数
        for (int i = 0; i < k - 1; i++) {
            sum += a[i];
            cnt.merge(a[i], 1, Integer::sum); // 如果a[i]已经在cnt中，合并其计数，否则添加计数为1
        }

        // 从k个数开始，移动窗口并更新最大和
        for (int i = k - 1; i < a.length; i++) {
            sum += a[i]; // 添加当前数到和
            cnt.merge(a[i], 1, Integer::sum); // 更新当前数的计数
            if (cnt.size() >= m) {
                ans = Math.max(ans, sum); // 如果窗口中至少有m个不同元素，更新最大和
            }

            // 移出窗口的数是a[i-k+1]，从cnt中减去它的计数
            int out = a[i - k + 1];
            sum -= out;
            // 如果移出的数在cnt中的计数变为0，则从cnt中移除该数
            if (cnt.merge(out, -1, Integer::sum) == 0) {
                cnt.remove(out);
            }
        }

        return ans;
    }

    /**
     * 「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，
     * 若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。
     * 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。
     * 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
     *
     * 示例 1：
     *
     * 输入：cards = [1,2,8,9], cnt = 3
     *
     * 输出：18
     *
     * 解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。
     *
     * 示例 2：
     *
     * 输入：cards = [3,3,1], cnt = 1
     *
     * 输出：0
     *
     * 解释：不存在获取有效得分的卡牌方案。
     *
     * 提示：
     *
     * 1 <= cnt <= cards.length <= 10^5
     * 1 <= cards[i] <= 1000
     *
     * #include <stdio.h>
     * #include <stdlib.h>
     *
     * // 比较函数，用于整数数组的降序排序
     * int compare(const void *a, const void *b) {
     *     int int_a = *((int*)a);
     *     int int_b = *((int*)b);
     *
     *     if (int_a == int_b) return 0;
     *     else if (int_a < int_b) return 1; // 降序
     *     else return -1;
     * }
     *
     * int main() {
     *     int numbers[] = {3, 6, 2, 8, 4, 7};
     *     int size = sizeof(numbers) / sizeof(numbers[0]);
     *
     *     // 使用 qsort 进行排序
     *     qsort(numbers, size, sizeof(int), compare);
     *
     *     // 打印排序后的数组
     *     for (int i = 0; i < size; i++) {
     *         printf("%d ", numbers[i]);
     *     }
     *     printf("\n");
     *
     *     return 0;
     * }
     *
     * // 定义一个宏，用于获取两个数中的最大值
     * #define MAX(a,b) ((b)>(a)?(b):(a))
     *
     * // qsort的比较函数，用于从大到小排序整数数组
     * int cmp(int* a, int* b) {
     *     return *a - *b;
     * }
     *
     * // 尝试替换数组中的一个元素以获得最大的偶数和
     * // cards: 整数数组
     * // cardsSize: 数组的大小
     * // cnt: 已经选择的元素数量
     * // s: 当前选择的元素之和
     * // x: 要替换的元素
     * int replace_sum(int* cards, int cardsSize, int cnt, int s, int x) {
     *     for (int i = cnt; i < cardsSize; i++) {
     *         // 找到一个奇偶性与 x 不同的最大数
     *         if (cards[i] % 2 != x % 2) {
     *             // 用找到的数替换 x，并计算新的和
     *             return s - x + cards[i];
     *         }
     *     }
     *     // 如果没有找到合适的数，返回0
     *     return 0;
     * }
     *
     * // 计算最大得分
     * // cards: 整数数组
     * // cardsSize: 数组的大小
     * // cnt: 需要选择的元素数量
     * int maxmiumScore(int* cards, int cardsSize, int cnt) {
     *     // 使用qsort对数组进行降序排序
     *     qsort(cards, cardsSize, sizeof(int), cmp);
     *     int s = 0;
     *     // 计算最大的 cnt 个数之和
     *     for (int i = 0; i < cnt; i++) {
     *         s += cards[i];
     *     }
     *     // 如果 s 是偶数，直接返回 s
     *     if (s % 2 == 0) {
     *         return s;
     *     }
     *
     *     // 如果 s 是奇数，尝试替换最后一个元素 x
     *     int x = cards[cnt - 1];
     *     int ans = replace_sum(cards, cardsSize, cnt, s, x); // 尝试替换 x
     *
     *     // 遍历前 cnt-1 个数，找到一个最小的奇偶性和 x 不同的数
     *     for (int i = cnt - 2; i >= 0; i--) {
     *         if (cards[i] % 2 != x % 2) {
     *             // 尝试替换并更新答案
     *             ans = MAX(ans, replace_sum(cards, cardsSize, cnt, s, cards[i]));
     *             break; // 找到第一个符合条件的数后即可停止循环
     *         }
     *     }
     *     // 返回最终的最大得分
     *     return ans;
     * }
     * @param cards
     * @param cnt
     * @return
     */
    public int maxmiumScore(int[] cards, int cnt) {
        Arrays.sort(cards);
        int n = cards.length;
        int s = 0;
        for (int i = n - cnt; i < n; i++) {
            s += cards[i]; // 最大的 cnt 个数之和
        }
        if (s % 2 == 0) { // s 是偶数
            return s;
        }

        int x = cards[n - cnt];
        int ans = replaceSum(cards, cnt, s, x); // 替换 x
        for (int i = n - cnt + 1; i < n; i++) {
            if (cards[i] % 2 != x % 2) { // 找到一个最小的奇偶性和 x 不同的数
                ans = Math.max(ans, replaceSum(cards, cnt, s, cards[i])); // 替换
                break;
            }
        }
        return ans;
    }

    private int replaceSum(int[] cards, int cnt, int s, int x) {
        for (int i = cards.length - cnt - 1; i >= 0; i--) {
            if (cards[i] % 2 != x % 2) { // 找到一个最大的奇偶性和 x 不同的数
                return s - x + cards[i]; // 用 cards[i] 替换 s
            }
        }
        return 0;
    }
}

